package com.aididi.jichu;

/**
 * @Auther: zx.xu
 * @Description:    java实现两个有序单链表的合并
 *  如  输入： 1->2->4, 1->3->4
 *      输出： 1->1->2->3->4->4
 */
public class MergeTwoList {

    /**
     * 思路是新建一个带头节点的链表，然后根据比较两个节点的值得大小，
     * 把小的那个存到新建的链表中，之后判断是否两个链表中有一个没有遍历完，
     * 把它添加到尾部即可，然后返回头节点的下一个节点即可。
     *
     * @param list1 链表一
     * @param list2 链表二
     * @return 新建的链表
     */
    public static ListNode mergerTwoList(ListNode list1, ListNode list2) {
        ListNode newNode = new ListNode(0);
        ListNode preNode = newNode;

        while (list1 != null && list2 != null) {
            if (list1.val >= list2.val) {
                newNode.next = list2;
                newNode = newNode.next;
                list2 = list2.next;
            } else {
                newNode.next = list1;
                newNode = newNode.next;
                list1 = list1.next;
            }
        }
        if (list1 == null) {
            newNode.next = list2;
        } else {
            newNode.next = list1;
        }
        return preNode.next;
    }


    public static void main(String[] args) {
        ListNode newNode = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(5);
        newNode.next = node1;
        node1.next = node2;
//        node2.next = node3;
        node3.next = node4;
        ListNode preNode = mergerTwoList(newNode, node3);
        while (preNode != null) {
            System.out.println(preNode.val);
            preNode = preNode.next;
        }

    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}